//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 4669 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution5 {
    /**
     * 解题思路：动态规划
     * 1.找规律， 字符串的正序和逆序结果一致，当字符串长度小于等于3，且字符串的头尾字符相同，则该字符串是回文数；
     *  当字符串长度大于3，且字符串头尾字符相同，则需要判断子字符串（头指针右移1位，尾指针左移1位）是否是回文数，如是，则该字符串也是回文数
     * 2.dp[l][r]: 表示字符串头指针l，尾指针r中截取出来的字符串是回文数（true)
     * 3.推导公式为 dp[l][r] = dp[l+1][r-1] = true;
     * 4.数组初始化： dp[0][0]=true;
     * 5.遍历顺序：第一层遍历从左往右遍历，从位置1开始遍历，遍历截止条件为尾指针不超过字符串长度；第二次遍历从左往右遍历，从位置0开始遍历，遍历截止条件为头指针不超过尾指针
     * <p>
     * 执行耗时:85 ms,击败了53.85% 的Java用户
     * 内存消耗:44.7 MB,击败了28.62% 的Java用户
     */
    public String longestPalindrome(String s) {
        if(s.length() <= 1) return s;
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[chars.length][chars.length];
        dp[0][0] = true;
        int maxLen = 1;
        int start = 0, end = 0;
        for (int r = 1; r < chars.length; r++) {
            for (int l = 0; l < r; l++) {
                if(chars[r] == chars[l] && ((r - l <=2) || dp[l+1][r-1])) {
                    dp[l][r] = true;
                    if((r - l + 1) > maxLen) {
                        maxLen = r - l + 1;
                        start = l;
                        end = r;
                    }
                }
            }
        }
        return s.substring(start, end+1);

    }

    public static void main(String[] args) {
        System.out.println(new Solution5().longestPalindrome("babad"));
        System.out.println(new Solution5().longestPalindrome("abcba"));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
